1. Field of the Invention
The invention relates to a method for determining a route from a departure point to a destination, which is based on a digital map showing a real road network in segments with resistances and nodes, in which route segments are optimized by means of a route-searching algorithm and are stored in a route table, and at least one intermediate destination is predetermined. The invention also relates to an apparatus for determining a route from a departure point to a destination by the aforesaid method, which has a digital map stored in a memory.
2. Description of the Related Art
In means of locomotion, for example motor vehicles, airplanes or ships, permanently installed navigation systems guide the operator of the means of locomotion rapidly, simply and safely to a desired destination without the need for any prior, tedious route planning and for the acquisition and study of appropriate map material. To this end, appropriate navigation data based on, for example, maps, country maps or road maps, are stored in the navigation system, for example on CD-ROM. The navigation device uses, for example, GPS (global positioning system) to determine the instantaneous position and to calculate the required navigation instructions that will lead to a predetermined destination. The navigation data in this case preferably contain data about streets and roads for motor vehicles.
In conventional navigation systems, the driver of a motor vehicle can in various ways influence the course of a route to be calculated, namely by selecting cog different optimization criteria, such as xe2x80x9cshort routexe2x80x9d, xe2x80x9cfast routexe2x80x9d, xe2x80x9cavoid superhighwaysxe2x80x9d, by influencing road sections manually or by traffic telecommunications, which in the route calculation are then by-passed or facilitated, or by defining one or more intermediate destinations which the driver then passes sequentially on his way to the final destination. If the driver wishes xe2x80x9cto travel from Kassel to Minden via Hannoverxe2x80x9d, only the last-said alternative is open to him. In Hannover, he must define an intermediate destination, which, for example, is the center of the city, after which two route calculations are made. A first route from Kassel to Hannover and a second route from Hannover to Minden are calculated. Linking the two routes together then gives the overall route. With the Alpine navigation system xe2x80x9cGP Shuttle, NVE-N055VPxe2x80x9d, for example, it is possible to select up to five intermediate destinations.
However it is a disadvantage that, when intermediate destinations are used, several route calculations, independent of each other, must be performed, their number depending on the number of intermediate destinations. Namely, it is first necessary to calculate the partial routes from the current position to the intermediate destination, then from said intermediate destination to the next one and finally to the actual destination. In this manner, however, the partial routes and not the overall one are optimized. Even when the indicated intermediate destination is not a city but a region, for example the region of the city of Hannover, the optimization of the route is carried out only as far as the boundary of the region so that the first partial route in the afore-described case ends somewhere at the outskirts of the city of Hannover. The exact location of this point on the periphery of Hannover depends only on the route from the departure point to this intermediate destination. Optimization of the point on the periphery of Hannover or of the subsequent route, for example, to the final destination or to the next intermediate destination, however, is not possible. In the area of the intermediate destination, this may result in unfavorable routing, nonsensical turns or avoidable city crossings.
The object of the present invention is to provide an improved method of the above-described type for determining a route from a departure point to a final destination based on a digital map, which represents a real road network with segments with resistances and nodes, which method eliminates the above-said disadvantages and ensures calculation of an optimal route, even when the user of a navigational method specifies intermediate destinations.
This method according to the invention comprises the steps of:
a) predetermining at least one intermediate destination through which the route must pass, each intermediate destination consisting of a respective transition region formed by a corresponding group of segments;
b) then optimizing segments for the route by means of a route search ok algorithm to obtain optimized segments and storing the optimized segments in a route table, and
c) minimizing an overall resistance of the route from the departure point to the final destination, with the proviso that the route is constrained to pass through the respective transition region of each intermediate destination.
The advantage of this is that the determination of the route to be calculated can be intentionally influenced by specifying transition regions (via areas). In contrast to conventional methods with intermediate destinations, the route is optimized from the departure position through the transition region to the destination as a whole and not in sections. Moreover, the driver need not worry about the definition of an actual intermediate destination. The use of the invention ensures that, after the calculation of the route, at any point in time, the optimum route from any possible departure point or any possible position of a motor vehicle to the final destination is possible by passing through the transition region or transition regions. In this manner, the distance to the destination and the remaining travel time or the estimated time of arrival can be indicated. In the route calculation from the departure point to the final destination, besides the conventional, predeterminable criteria, for example xe2x80x9cshort routexe2x80x9d, xe2x80x9cfast routexe2x80x9d or the like, one or more via areas are taken into consideration, the via areas being included by the user into the calculated route in a predetermined sequence.
In a preferred embodiment, each intermediate destination is defined as a transition region in the form of a surface region of the digital map, and corresponding segments located in the area of the transition region in question are assigned and stored in a transition region list. A first segment optimization is performed starting from a destination segment corresponding to the destination, and the result is stored in a first route table, additional sectional segment optimizations corresponding to the number of predetermined transition regions being performed and stored in separate sectional route tables. At the end of the first segment optimization, the segments stored in the originally initialized and destination-initialized transition region list with the corresponding resistances from the first route table are updated. Furthermore, at the beginning of each sectional segment optimization, the current resistances of the segments of the transition region list are entered into the originally initialized sectional route table. Furthermore, at the end of the first and up to the penultimate sectional segment optimization, the resistances of the segments stored in the current transition region list with the resistances of the corresponding segments of the sectional route table are updated, and after the last sectional segment optimization, starting with the last sectional route table, and up to the first route table, a route list is compiled from these tables so as to minimize the overall resistance of the route from the departure point through one or more intermediate destinations to the final destination.
Advantageously, the compilation of the route list is accomplished in that, starting with the sectional route table of the last-performed sectional segment optimization, the relevant segments are entered into the route list one after the other until no follower to a segment is defined in the sectional route table. The procedure is continued in the same manner with this segment and with a next and further sectional route table up to the first route table, the sequence in which the sectional route tables are processed being predetermined in the transition region list.
In a preferred embodiment, a transition region description list and a transition region index table are stored in the transition region list the transition region index table containing an assignment of transition regions to the transition region description list and route tables, and the transition region description list containing segments with corresponding resistances and assigned to a transition region.
In this case, the destination with resistance zero is the first entry into the transition region description list.
In the original initialization, all resistances are set equal to infinity and any stored followers are cancelled, whereas for the destination initialization the resistances of a segment corresponding to the destination are set equal to zero.
Advantageously, the chosen transition region is a rectangle, polygon, ellipse or circle around a prominent point, particularly a city, congested area or superhighway exit.
The description of the transition regions may purposely be left vague in spatial terms, because the driver only wants to influence the overall route.
In addition, network influencing through telecommunication and/or user-defined manipulations, for example xe2x80x9ctraffic jam aheadxe2x80x9d obstructions, is advantageously taken into consideration in the route calculation. In this manner, it is possible to influence the route dynamically through a telecommunication service provider, for example to guide traffic flow. The navigation computer in the motor vehicle remains here fully autonomous and can react in a self-sufficient manner and rapidly when the driver deviates from the route.
According to the invention, the apparatus for performing the method is provided with a device for entering and defining at least one intermediate destination defined as a transition region in the form of a surface region of the digital map. Also provided is a storage device for storing the properties and, if necessary, the sequence of the transition region or regions, namely an index memory.
In an advantageous embodiment the apparatus comprises a navigation computer, a data storage device containing the digital map as an image of the real road network, a sensing device, a position-finding device, the index memory, an interface, a loudspeaker, a display and an input device.